package leetcode.slidingwindow;

import java.util.Arrays;

//713. 乘积小于K的子数组
public class NumSubarrayProductLessThanK {

    public static void main(String[] args) {

        int[] data = {10, 5, 2, 6};
        System.out.println(numSubarrayProductLessThanKP(data, 100));
    }

    //双指针
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length;
        int left = 0;
        int res = 0;
        int mul = 1;
        if (k <= 1) {
            return 0;
        }

        int right = 0;
        while (right < n) {
            int x = nums[right];
            mul *= x;
            while (mul >= k) {
                mul /= nums[left++];
            }

            res += right - left + 1;
            right++;

        }
        return res;
    }

    //滑动窗口----本题有一个规律
    public static int numSubarrayProductLessThanK2(int[] nums, int k) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        int res = 0;
        int mul = 1;
        while (right < n) {
            int x = nums[right];
            //如果当前元素大于k，直接跳过该元素，left指针指向其后面
            right++;
            if (x >= k) {
                left = right;
                //重置mul
                mul = 1;
                continue;
            }
            mul *= x;
            //当乘积不小于k的时候，移动左边界缩小区域
            while (mul >= k) {
                mul = mul / nums[left];
                left++;
            }
            res = res + (right - left);

        }
        return res;
    }

    // 二战---暴力
    public static int numSubarrayProductLessThanKP(int[] nums, int k) {
        int res = 0;
        long count = Arrays.stream(nums).filter(item -> item < k).count();
        res += count;
        for (int i = 0; i < nums.length; i++) {
            int mul = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                mul *= nums[j];
                if (mul < k) {
                    res++;
                } else {
                    break;
                }
            }
        }
        return res;
    }


    // 双指针，类似快慢指针，right控制乘法，left控制除法
    public static int numSubarrayProductLessThanKP2(int[] nums, int k) {
        int mul = 1;
        int left = 0;
        int n = nums.length;
        int res = 0;
        // 由于数组内是正整数
        if (k <= 1) {
            return 0;
        }
        int right = 0;
        while (right < n) {
            mul *= nums[right];
            while (mul >= k) {
                mul /= nums[left++];
            }
            res += right - left + 1;
            right++;
        }

        return res;
    }

}
